/**
 * 剑指 Offer 26. 树的子结构
 * https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
 */
public class Solutions_Offer_26 {
    public static void main(String[] args) {
        TreeNode A = new TreeNode(3);
        A.left = new TreeNode(4);
        A.left.left = new TreeNode(1);
        A.left.right = new TreeNode(2);
        A.right = new TreeNode(5);

        TreeNode B = new TreeNode(4);
        B.left = new TreeNode(1);  // output: true

//        TreeNode B = new TreeNode(3);
//        B.left = new TreeNode(5);
//        B.right = new TreeNode(5);  // output: false

        boolean result = isSubStructure(A, B);
        System.out.println(result);
    }

    /**
     * A 中有出现和 B 相同的结构和节点值，B 即是 A 的一个子结构
     */
    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            // 空树不是任何一个树的子结构
            return false;
        }
        if (A.val == B.val) {
            // 遍历比较
            boolean res = compareABTree(A, B);
            if (res) {
                return true;
            }
        }
        // 左子树或右子树，有一侧能够把 B 遍历完，即 return true
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    /**
     * 同时递归判断 A 与 B 的结构与节点值
     * @return B 的左右子树能够都遍历完，说明 B 是 A 的一个子结构，否则不是
     */
    public static boolean compareABTree(TreeNode A, TreeNode B) {
        if (B == null) {
            // B 已经遍历完，return true
            return true;
        }
        // 结束条件：B 还未遍历完，A 已经遍历完了；还有两个节点值不同的情况，都说明 B 不是 A 的一个子结构
        if (A == null || A.val != B.val) {
            return false;
        }
        // 左右子树，必须都能够把 B 给遍历完，才能 return true
        return compareABTree(A.left, B.left) && compareABTree(A.right, B.right);
    }
}
